/**
 * @author LKQ
 * @date 2022/2/14 9:52
 * @description 二分查找 如果mid是偶数，则比较nums[mid] 和 nums[mid + 1]是否相等，如果mid是奇数，则比较nums[mid-1]和nums[mid]是否相等
 */
public class Solution2 {
    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        int[] nums = {1, 1, 2, 3, 3, 4, 4, 8, 8};
        solution.singleNonDuplicate(nums);
    }
    public int singleNonDuplicate(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            // mid ^ 1, 如果 mid 为偶数，那么相当于 mid + 1, 为奇数，那么相当于 mid - 1
            if (nums[mid] == nums[mid ^ 1]) {
                // 相邻元素的结果是相等，则 mid < x
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return nums[low];
    }

}
